Developer CD Series 1998 April: Mac OS SDK/Dev.CD Apr 98 SDK1.toast/Development Kits (Disc 1)/QuickDraw 3D/Samples/SampleCode/Plug-in - WireFrame Renderer/SR_ClipUtilities.c

C/C++ Source or Header | 1997-08-14 | 12.9 KB | 513 lines | [TEXT/MPS ]

/******************************************************************************
 **                                                                             **
 **     Module:        SR_ClipUtilities.c                                         **
 **                                                                          **
 **                                                                          **
 **     Purpose:     Clipping utilities for Sample Renderer                     **
 **                                                                          **
 **                                                                          **
 **                                                                          **
 **     Copyright (C) 1996-1997 Apple Computer, Inc.  All rights reserved.     **
 **                                                                          **
 **                                                                          **
 *****************************************************************************/
#include "QD3D.h"
#include "QD3DMath.h"

#include "SR.h"
#include "SR_ClipUtilities.h"

#define    TRUNC(X)                (float)((long)(X))
#define SUBPIXEL_SNAP            ((float) 64.0)
#define SUBPIXEL_SNAP_INVERSE    ((float) 1.0 / (float) 64.0)


/*===========================================================================*\
 *
 *    Routine:    SRPointList_WDivide()
 *
 *    Comments:
 *
\*===========================================================================*/

void SRPointList_WDivide(
    TQ3RationalPoint4D         *in,
    unsigned long             numVertices,
    unsigned long             sizeOfIn)
{
    float                    w;
    long                    i;
    TQ3RationalPoint4D        *s = in;
    long                    ci;
    float                    cf;
    float                    c;
    float                    wInv;

    for (i = 0; i < numVertices; i++) {
        w = s->w;

        if (s->w != 0.0) {
            wInv = 1.0 / w;
        } else {
            wInv = kQ3MaxFloat;
        }

        c = s->x * wInv;
        ci = FLOAT_TRUNC_TO_LONG(c);
        cf = c - (float)ci;

        cf = FLOAT_ROUND_TO_LONG_POSITIVE(cf * SUBPIXEL_SNAP);
        cf = cf * SUBPIXEL_SNAP_INVERSE;

        s->x = (float)ci + cf;

        c = s->y * wInv;
        ci = FLOAT_TRUNC_TO_LONG(c);
        cf = c - (float)ci;

        cf = FLOAT_ROUND_TO_LONG_POSITIVE(cf * SUBPIXEL_SNAP);
        cf = cf * SUBPIXEL_SNAP_INVERSE;

        s->y = (float)ci + cf;

        s->z *= wInv;

        s = (TQ3RationalPoint4D *)((unsigned char *)s + sizeOfIn);

    }
}


/*===========================================================================*\
 *
 *    Routine:    SRPointList_ClipTestVertices()
 *
 *    Comments:    Check if we have any clipped-out vertices
 *
\*===========================================================================*/

void SRPointList_ClipTestVertices(
    TQ3RationalPoint4D         *deviceVertices,
    unsigned long             *clipFlags,
    long                     numVertices,
    float                     *clipPlanes,
    long                     *clipFound,
    long                     *allOut,
    unsigned long             sizeOfIn)
{
    long                i;
    float                x, y, z, w;
    long                clipFlag;
    TQ3RationalPoint4D    *s;
    float                xMin, xMax,
                        yMin, yMax,
                        zMin, zMax;

    s = deviceVertices;

    xMin = clipPlanes[0];
    xMax = clipPlanes[1];
    yMin = clipPlanes[2];
    yMax = clipPlanes[3];
    zMin = clipPlanes[4];
    zMax = clipPlanes[5];

    *clipFound = *allOut = 0;

    i = 0;
    while (i < numVertices) {
        clipFlag = 0;

        x = s->x;
        y = s->y;
        z = s->z;
        w = s->w;

        /*
          *  The view clip planes are defined by xmin, xmax, ymin, ymax,
          *    zmin, zmax. Clearly these planes are perpendicular to the
          *    appropriate axis.  For example, xmin is perpendicular to the YZ
          *    plane and defines the minimum x coordinate for clipping.
         *
         *  In this clip test, we allow the clipping planes to be any
         *  value.  They are not just limited to  -1,1 like in some
         *  clipping environments.  The only stipulation is that the
         *  min actually be less than the max for a plane combination.
         *
         *  The same set of tests is applied consistently to all point
         *    regardless of the sign of w.  Normally, only the geometry in front
         *  of the camera is desired so the tests for the positive- w space
         *  should be applied consistently.  Sometimes, the geometry in the
         *  negative w space is desired too.  Then all the points should be
         *  retraversed with the negative-w tests applied to all points.
         */
        if (x < xMin * w) {
            clipFlag |= SR_MIN_X;
        }
        if (x > xMax * w) {
            clipFlag |= SR_MAX_X;
        }

        if (y < yMin * w) {
            clipFlag |= SR_MIN_Y;
        }
        if (y > yMax * w) {
            clipFlag |= SR_MAX_Y;
        }

        if (z - w * zMin < 0.0) {
            clipFlag |= SR_MIN_Z;
        } else if (z - w * zMax > 0.0) {
            clipFlag |= SR_MAX_Z;
        }

        /*
         *  All vertices are out if & of all points is not 0
         */
        if (i == 0) {
            *allOut = clipFlag;
        } else {
            *allOut &= clipFlag;
        }

        *clipFound |= clipFlag;

        /*
         *  Vertices are clipped if | of all clip flags is 0
         */
        clipFlags[i] = clipFlag;

        s = (TQ3RationalPoint4D *)((unsigned char *)s + sizeOfIn);

        i++;
    }
}

#define    OUTPUT_POINT(DEST, SRC_POINT)                            \
{                                                                \
    double    w;                                                    \
                                                                \
    w = SRC_POINT->w;                                            \
                                                                \
    DEST->x = (double)SRC_POINT->x / w;                            \
    DEST->y = (double)SRC_POINT->y / w;                            \
    DEST->z = (double)SRC_POINT->z / w;                            \
    DEST->w = 1.0;                                                \
}

#define    OUTPUT_POINT_INTERPOLATE(DEST, PREV, CURR, PARAM)        \
{                                                                \
    double    w;                                                    \
    double    oneMinusPARAM;                                        \
                                                                \
    oneMinusPARAM = (double)1.0 - (double)PARAM;                \
                                                                \
    w = oneMinusPARAM * (double)PREV->w + (double)PARAM * (double)CURR->w;                \
                                                                                        \
    DEST->x = (oneMinusPARAM * (double)PREV->x + (double)PARAM * (double)CURR->x) / w;    \
    DEST->y = (oneMinusPARAM * (double)PREV->y + (double)PARAM * (double)CURR->y) / w;    \
    DEST->z = (oneMinusPARAM * (double)PREV->z + (double)PARAM * (double)CURR->z) / w;    \
    DEST->w = 1.0;                                                \
}

#define COMPUTE_PLANE_INTERSECTIONS(VALUES, COORDS, CLIP_PLANES)            \
{                                                                            \
    int        j;                                                                \
    double    w = COORDS[3];                                                    \
                                                                            \
    for (j = 0; j < 6; j++) {                                                \
          /* For each clip plane; compute parametric intersection. */            \
        VALUES[j] = (double)COORDS[j >> 1] - w * (double)CLIP_PLANES[j];    \
    }                                                                        \
}


#define    BUMP_DEST_POINTERS                                                    \
    clippedVertices =(TQ3RationalPoint4D *)((unsigned char *)clippedVertices\
        + sizeOfClippedVertex);



/*===========================================================================*\
 *
 *    Routine:    SRPointList_ClipVertices()
 *
 *    Comments:    Given a set of vertices, compute a clipped set.
 *
\*===========================================================================*/

void SRPointList_ClipVertices(
    TQ3RationalPoint4D         *vertices,
    long                     sizeOfVertex,
    TQ3RationalPoint4D         *clippedVertices,
    long                     sizeOfClippedVertex,
    unsigned long             *clipFlags,
    long                     *clippedVertexFlags,
    long                     sourceNumberOfPoints,
    long                     *destNumberOfPoints,
    float                     *clipPlanes,
    long                    mode)
{
    long                    i, j;
    float                    *coords;
    TQ3RationalPoint4D        *sPrevious,
                            *sCurrent;
    double                    previousValues[6],
                            currentValues[6];
    double                    prevParametricValue,
                            currParametricValue;
    double                    parametricValue;
    long                    lineClipped;

    (*destNumberOfPoints) = 0;

    sPrevious = vertices;

    /* if first point not clipped then output it */
    if ((clipFlags[0] & SR_CLIP_ALL) == 0) {
        OUTPUT_POINT(clippedVertices, sPrevious);
        clippedVertexFlags[*destNumberOfPoints] = SR_DRAW_NEXT;
        (*destNumberOfPoints)++;
        BUMP_DEST_POINTERS;
    }

    sCurrent =
        (TQ3RationalPoint4D *)((unsigned char *)sPrevious + sizeOfVertex);

    for (i = 1; i < sourceNumberOfPoints; i++) {
        if ((clipFlags[i - 1] & SR_CLIP_ALL) & (clipFlags[i] & SR_CLIP_ALL)) {
            /*
             *  Previous and current are outside; do nothing
             */
        } else if (!((clipFlags[i - 1] & SR_CLIP_ALL)     |
                     (clipFlags[i]     & SR_CLIP_ALL))) {
            /*
             *  Previous and current vertex are inside turn
             *  on draw vector bit and output current vertex
             */
            OUTPUT_POINT(clippedVertices, sCurrent);
            clippedVertexFlags[*destNumberOfPoints] = SR_DRAW_NEXT;
            (*destNumberOfPoints)++;
            BUMP_DEST_POINTERS;
        } else {
            /*
                * For each clip plane; compute parametric clip with
              * previous and current point.
              */

            /* point to current XYZW */
            coords = (float *)&sPrevious->x;
            COMPUTE_PLANE_INTERSECTIONS(previousValues, coords, clipPlanes);

            /* point to current XYZW */
            coords = (float *)&sCurrent->x;
            COMPUTE_PLANE_INTERSECTIONS(currentValues, coords, clipPlanes);

            prevParametricValue = 0.0;
            currParametricValue = 1.0;

            lineClipped = 1;

            for (j = 0; j < 6; j++) {
                /*
                  *  If previous flag and current differ then we cross
                  *  a clip boundary and we must compute the intersection.
                  */
                if (lineClipped) {
                    if (((clipFlags[i - 1] ^ clipFlags[i]) >> j) & 1) {

                        parametricValue =
                            previousValues[j] /
                                (previousValues[j] - currentValues[j]);

                        if ((clipFlags[i] >> j) & 1) {
                            if (currParametricValue > parametricValue) {
                                currParametricValue = parametricValue;
                            }
                        } else {
                            if (prevParametricValue < parametricValue) {
                                prevParametricValue = parametricValue;
                            }
                        }
                    } else {
                        lineClipped = !((clipFlags[i] >> j) & 1);
                    }

                    lineClipped =
                        lineClipped &
                            (prevParametricValue < currParametricValue);
                }
            }

            if (lineClipped) {
                /*
                  *  Compute clip for previous vertex
                  */
                if (prevParametricValue > 0.0) {
                    OUTPUT_POINT_INTERPOLATE(
                        clippedVertices,
                        sPrevious,
                        sCurrent,
                        prevParametricValue);
                    /*
                     *  Point is clipped on the way into the visible region
                     *  so set draw bit
                     */
                    clippedVertexFlags[*destNumberOfPoints] = SR_DRAW_NEXT;
                    (*destNumberOfPoints)++;
                    BUMP_DEST_POINTERS;
                }

                /*
                 *  Compute clip for current vertex
                 */
                if (currParametricValue < 1.0) {
                    OUTPUT_POINT_INTERPOLATE(
                        clippedVertices,
                        sPrevious,
                        sCurrent,
                        currParametricValue);
                    /*
                     *  Point is clipped on the way out of the visible region
                     *  so turn off draw bit
                     */
                    clippedVertexFlags[*destNumberOfPoints] &= ~SR_DRAW_NEXT;
                    (*destNumberOfPoints)++;

                    BUMP_DEST_POINTERS;
                } else {
                    OUTPUT_POINT(clippedVertices, sCurrent);

                    /*
                     *  Point is inside visible region so turn on draw bit
                     */
                    clippedVertexFlags[*destNumberOfPoints] = SR_DRAW_NEXT;
                    (*destNumberOfPoints)++;
                    BUMP_DEST_POINTERS;
                }
            }
        }

        /*
         *  Update previous and current pointers
         */
        sPrevious = sCurrent;
        sCurrent = (TQ3RationalPoint4D *)
                        ((unsigned char *)sPrevious + sizeOfVertex);
    }

    /*
     *  If we have fewer than 3 vertices then don't clip from the last to the
     *  first vertex since that doesn't make any sense.
     */
    if (sourceNumberOfPoints < 3) {
        return;
    }

    /*
     *  'mode' is either polygon or polyline.  When mode is polygon (0) then
     *  we must clip from the last vertex to the first vertex.  When mode is
     *  polyline (1) then we don't do this clip.
     */
    if (mode == DO_POLYLINE) {
        return;
    }

    /*
     *  If first vertex is in then do nothing.
     *  If first vertex is clipped and last vertex is displayed then compute
     *    another clip point from last vertex to first
     */
    if (!((clipFlags[0] & SR_CLIP_ALL) |
        (clipFlags[sourceNumberOfPoints - 1] & SR_CLIP_ALL))) {
        /*
         *  First and last are inside; do nothing since
         *  draw bit of last should be set
         */
    } else {
        sPrevious = &vertices[sourceNumberOfPoints - 1];

        coords = (float *)&sPrevious->x;
        COMPUTE_PLANE_INTERSECTIONS(previousValues, coords, clipPlanes);

        sCurrent = vertices;

        coords = (float *)&sCurrent->x;
        COMPUTE_PLANE_INTERSECTIONS(currentValues, coords, clipPlanes);

        /* compute clip from last vertex to first vertex */
        prevParametricValue = 0.0;
        currParametricValue = 1.0;

        lineClipped = 1;

        for (j = 0; j < 6; j++) {
            /*
              *  If previous flag and current differ then we cross
              *  a clip boundary and we must compute the intersection.
              */
            if (lineClipped) {
                if (((clipFlags[sourceNumberOfPoints - 1] ^ clipFlags[0]) >> j) & 1) {
                    parametricValue = previousValues[j] /
                                        (previousValues[j] - currentValues[j]);

                    if ((clipFlags[0] >> j) & 1) {
                        if (currParametricValue > parametricValue) {
                            currParametricValue = parametricValue;
                        }
                    } else {
                        if (prevParametricValue < parametricValue) {
                            prevParametricValue = parametricValue;
                        }
                    }
                } else {
                    lineClipped = !((clipFlags[0] >> j) & 1);
                }

                lineClipped = lineClipped &
                                (prevParametricValue < currParametricValue);
            }
        }

        if (lineClipped) {
            /*
              *  Compute clip for previous vertex
              */
            if (prevParametricValue > 0.0) {
                OUTPUT_POINT_INTERPOLATE(
                    clippedVertices,
                    sPrevious,
                    sCurrent,
                    prevParametricValue);
                clippedVertexFlags[*destNumberOfPoints] = SR_DRAW_NEXT;
                (*destNumberOfPoints)++;
                BUMP_DEST_POINTERS;
            }

            /*
             *  Compute clip for current vertex
             */
            if (currParametricValue < 1.0) {
                OUTPUT_POINT_INTERPOLATE(
                    clippedVertices,
                    sPrevious,
                    sCurrent,
                    currParametricValue);
                clippedVertexFlags[*destNumberOfPoints] &= ~SR_DRAW_NEXT;
                (*destNumberOfPoints)++;
                BUMP_DEST_POINTERS;
            } else {
                OUTPUT_POINT(clippedVertices, sCurrent);

                /*
                 *  Point is clipped so compute last vertex and don't
                 *  display it
                 */
                clippedVertexFlags[*destNumberOfPoints] = SR_DRAW_NEXT;
                (*destNumberOfPoints)++;
                BUMP_DEST_POINTERS;
            }
        }
    }
}